Faith Ellen
Abstract:
Patrascu recently introduced a number-on-the-forehead communication
model in which one player only participates by sending advice
to a second player at the beginning of the protocol. He gave reductions
from the problem of solving an asymmetric version of set-disjointness in
this model to a diverse collection of natural dynamic data structure
problems in the cell probe model. He also conjectured that, for any hard
problem in the standard two party communication model, the asymmetric
version of the problem is hard in his model.
This talk will present several surprising results about Patrascu's model,
including a simple, deterministic protocol for the asymmetric
version of equality with $O(\log n)$ communication complexity
and a deterministic protocol for the asymmetric version of the set
disjointness problem with $O(\sqrt{n})$ communication complexity.
(In the two party communication model, equality has large deterministic
communication complexity and set disjointness has large randomized
communication complexity.) The randomized and deterministic communication
complexities of problems in Patrascu's model will also be shown to
differ by no more than a multiplicative factor of $O(\log n)$.
This work is joint with Arkadev Chattopadhyay, Jeff Edmonds,
and Toni Pitassi and appeared at SODA 2012.